import random

def sort(toSort):
    """Sorts all of the elements in the provided list using only three stacks, and 
    no additional memory."""

    a = []
    b = []
    c = toSort[:]

    # This problem appears in the ACM. We must sort the elements in the given list
    # using no memory other than the three stacks, and at each step, we can only
    # inspect the top element of each stack and respond by moving a single card from
    # one stack to another. We make use of an "alarm" that triggers when all of the 
    # elements appear in sorted order in the first stack. This alarm is not subject
    # to the same constraints.

    while not isFinished(a,b,c):
        if len(a) == 0 or (len(b) == 0 or b[-1] < a[-1]) and (len(c) == 0 or c[-1] < a[-1]):
            # both b and c are < a, so move the greater of the two to a
            if len(b) == 0 or (len(c) != 0 and c[-1] > b[-1]):
                a.append(c.pop())
            else:
                a.append(b.pop())
        else: 
            # one of b and c is greater than a. move a on top of the lower of the two
            if len(b) == 0 or (len(c) != 0 and c[-1] > b[-1]): 
                b.append(a.pop())
            else:
                c.append(a.pop())

    return a

def sort_harder(toSort):
    """Sorts all of the elements in the provided list using only two stacks, a single
    int variable, and no additional memory."""

    a = []
    b = []
    c = toSort[:]

    # This version of the problem has the same constraints, except that the stack 'b'
    # may only contain a single element at a time (in other words it's just an nullable int)
    # Interestingly, this additional constraint forces an even more elegant solution.
    # We take the same approach of maintaining 'a' in decending sorted order. Whenever 
    # we see an element at the top of 'c' that's greater than the top element of 'a', 
    # we stash it in 'b' and move elements from 'a' to 'c' until it is less than the element
    # at the top of 'a' or 'a' is empty. At this point we will have found the correct position
    # in 'a' for that element in 'b', and it get's moved to 'a'.

    while not isFinished(a,b,c):
        if len(b) > 0:
            if len(a) == 0 or b[-1] < a[-1]:
                a.append(b.pop())
            else:
                c.append(a.pop())
        elif len(a) == 0 or c[-1] < a[-1]:
            a.append(c.pop())
        else:
            b.append(c.pop())

    return a

def isFinished(a,b,c):
    if (len(b) > 0 or len(c) > 0):
        return False
    for i in range(len(a) - 1):
        if a[i] < a[i+1]:
            return false
    return True

if __name__ == "__main__":
    toSort = random.sample(range(1000), 20)
    print(toSort)

    print(sort(toSort))

    print(sort_harder(toSort))